package main

import (
	"fmt"
	"strings"
)

//link: https://leetcode-cn.com/problems/sliding-puzzle/
func main() {
	board := [][]int{{1, 2, 3}, {4, 0, 5}}
	fmt.Println(slidingPuzzle(board))
}

var neighbors = [6][]int{{1, 3}, {0, 2, 4}, {1, 5}, {0, 4}, {1, 3, 5}, {2, 4}}

func slidingPuzzle(board [][]int) int {
	const target = "123450"

	s := make([]byte, 0)
	for _, r := range board {
		for _, v := range r {
			s = append(s, '0'+byte(v))
		}
	}
	start := string(s)
	//如果开始节点就是目标节点则返回
	if start == target {
		return 0
	}
	//获取0的左右节点的状态值
	get := func(status string) (ret []string) {
		s := []byte(status)
		x := strings.Index(status, "0")
		for _, y := range neighbors[x] {
			//变换状态
			s[x], s[y] = s[y], s[x]
			ret = append(ret, string(s))
			//恢复状态
			s[x], s[y] = s[y], s[x]
		}
		return ret
	}

	type pair struct {
		status string
		step   int
	}

	q := []pair{{start, 0}}
	seen := map[string]bool{start: true}
	for len(q) > 0 {
		p := q[0]
		q = q[1:]
		//寻找左右替换了的状态
		for _, next := range get(p.status) {
			//若没找过
			if !seen[next] {
				if next == target {
					return p.step + 1
				}
				seen[next] = true
				q = append(q, pair{next, p.step + 1})
			}
		}
	}
	return -1
}
